競プロ典型 90 問 027

(工事中)

解き方

解答例

下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。

code: C

typedef struct tree {

char c;

int is_end;

struct tree *ch;

struct tree *next;

} tree;

int main () {

int n = 0;

int res = 0;

tree *top = NULL;

res = scanf("%d", &n);

for (int k = 0; k < n; k++) {

tree **t = &top;

tree *parent = NULL;

int i = 0;

res = scanf("%s", s);

t = &((*t)->next);

}

if (*t == NULL) {

*t = (tree *)malloc(sizeof(tree));

if (*t == NULL) {

exit(0);

}

(*t)->is_end = 0;

(*t)->ch = NULL;

(*t)->next = NULL;

}

t = &((*t)->ch);

}

i++;

}

if((*t)->is_end <= 0) {

printf("%d\n", k+1);

}

(*t)->is_end = 1;

}

return 0;

}

私の提出一覧

table: submissions_atcoder_typical90_027

提出のURL 提出時刻 結果 備考

感想

ローカルにおいてあったzakkan.txt（雑感）には、まだ書かれていないので、こっちに直接書く

今なら全て読み込んだ後にソートすることを考える気もするが、当時はそんなこと思いつかなかったのか、全て読み込んでから答えることに抵抗があったのか、わざわざトライ木を作っている。

記憶が確かなら、このときはまだトライ木をちゃんと認識しておらず、これがトライ木（擬き）である自覚はなかった気がする

どちらかというと、すでに登録済みの文字列を受理するオートマトンを作った気でいた気がする。あるいみこれも再開発かな

再開発→再発明（？）